/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/max-area-of-island
   @Language: C++
   @Datetime: 19-05-13 17:24
   */

class Solution {
public:
	/**
	 * @param grid: a 2D array
	 * @return: the maximum area of an island in the given 2D array
	 */
	int maxAreaOfIsland(vector<vector<int> > &grid) {
		// Write your code here
		int area=0, n=grid.size(), m=grid[0].size();
		unordered_set<int> visit;
		for(int row=0; row<n; ++row){
			for(int col=0; col<m; ++col){
				if(grid[row][col]==0 || visit.count(col|(row<<8))) continue;
				queue<pair<int,int> > q;	// bfs
				int count=0;
				for(q.push(make_pair(row,col)); q.size(); q.pop()){
					const int i=q.front().first, j=q.front().second;
					if(i<0 || i>=n || j<0 || j>=m) continue;
					if(visit.count(j|(i<<8))) continue;
					if(grid[i][j]==0) continue;
					visit.insert(j|(i<<8));
					++count;
					q.push(make_pair(i+1,j));
					q.push(make_pair(i-1,j));
					q.push(make_pair(i,j+1));
					q.push(make_pair(i,j-1));
				}
				area=max(area,count);
			}
		}
		return area;
	}
};
